This invention relates generally to the field of computer system software and more specifically to the field of compilers.
As it is known in the art, software applications that are executed on a computer system are written in a high level computer language such as FORTRAN or "C". Before the application can be executed by the computer system, it must first be translated from the high level language down to a machine executable instruction stream. A software program known as a "compiler" uses input data about the type of computer system and the type of high level language in order to translate the application into machine code capable of being executed by the computer system.
The computer system is typically comprised of a number of functional units including a decode unit, an execution unit, and a memory unit. Each machine code instruction is decoded by the decode unit to determine the type of operation to be performed by the instruction. The instructions which are capable of being decoded and executed by the computer system are known as the instruction set of the computer. Typical instructions on a Reduced Instruction Set Computer (RISC) include a LOAD instruction and a STORE instruction.
In early computer systems, each instruction in a sequence was decoded and the associated function was performed before the decode of the following instruction in the sequence. Such an arrangement ensured that each operation was complete before the start of the next and that therefore any data dependencies between instructions were always satisfied before the instruction was decoded. A drawback of this arrangement was that only one unit of the computer system was functioning at any given time interval, while the other portions remained idle. Accordingly, because the computer system was not being fully utilized, the performance of the computer system was greatly reduced.
"Pipelined" architecture was developed in an effort to maximize the utilization of the computer system. In pipelined computer systems, after one instruction in the sequence was decoded by the decode unit and passed to the execution unit, the decode unit immediately began decoding the next instruction in the sequence. With such an arrangement the decode unit, the execution unit and the memory unit could all be operating on different instructions during any given time interval.
However, pipelined architectures still must honor dependencies between instructions in a sequence. For example, if one instruction in a sequence was to LOAD R1, (R2) (which acts to load a register R1 with the contents of memory at an address designated by R2) a memory read must be performed.
If the next instruction in the sequence is ADD R1, R5 (which acts to add the contents of the two registers), the ADD instruction can not be performed until the read of memory has been completed. As a result the computer system typically stalled the execution of instructions until the dependencies between successive instructions were resolved, again reducing the overall performance of the system.
In an effort to combat the performance reduction caused by stalls, the concept of rescheduling instructions arose. Rescheduling instructions involves reordering the sequence of instructions to place one or more other instructions in the sequence between instructions having dependencies that may result in a stall. With such an arrangement, functional work may be performed in instances where previously the machine was idle and thus the performance of the computer system is improved.
Compilers that reschedule instructions typically divide the instruction sequence into groups of instructions called basic blocks. A basic block is a group of instructions having only one entry point and one exit point. All instructions in the basic block are executed before exiting from the block. Therefore, instructions in the block may be rescheduled to any location in the block to alleviate stall situations caused by dependencies between instructions in the block as long as dependencies between instructions are obeyed.
However, for computer systems capable of executing a number of instructions at a time, short basic blocks of code do not provide a sufficient number of instructions for optimal rescheduling. In order to make additional instructions available for rescheduling, an approach known as "speculative scheduling" has been developed. According to the concept of speculative scheduling, instructions following a conditional branch instruction (and thus in a different basic block) may be rescheduled to precede the branch instruction. This rescheduled instruction is referred to as a "speculative instruction." After rescheduling, the speculative instruction is situated such that it will be executed before it is determined whether or not the branch is taken, and consequently before it is determined whether or not that speculative instruction need be executed at all. If it is determined that the speculatively executed instruction did not need to be executed, the instruction is said to be "mispredicted" and its result is ignored.
One problem that occurs with speculative scheduling arises from speculatively executed instructions which cause exceptions. An exception is raised when an error is detected by the computer system, such as a reference to an invalid address. Exceptions result in an interruption of the normal processing of the instruction sequence so that the error can be repaired and the instruction causing the error replayed before processing of the instruction sequence is resumed. If a speculatively executed instruction is mispredicted, and generates an exception, then a great deal of compute time is wasted handling an exception that would not have occurred had the speculative instruction been left in its original basic block.
Both hardware and software techniques have been developed to handle speculative exceptions. One hardware technique, described in U.S. Pat. No. 5,421,022, determines that there has been an exception condition caused by a speculative instruction, but withholds the signaling of an exception to the computer system until it is determined that the speculative instruction is in fact executed.
Software techniques typically do not have the capability to defer exceptions as done in hardware. However, one software method, described in U.S. patent application Ser. No. 08/270,192, filed Jul. 1, 1994 and entitled "A Software Mechanism for Accurately Handling Exceptions Generated by Instructions Scheduled Speculatively due to Branch Elimination" defers exceptions in the following manner: Using a technique called "hardware predication", branch instructions were eliminated by applying the condition evaluated by the branch as a predicate to each instruction controlled by the branch. Each instruction controlled by the branch was encoded with the location of the instruction's associated predicate. In addition, each instruction included a semaphore for indicating whether an exception occurred during the execution of the speculative instruction. The exception handler, before executing the code to correct the exception, first checked the predicate and the semaphore of the speculative instruction. If it was determined that the speculative instruction should not have been executed, the exception handler did not proceed with the exception routine.
Thus both hardware and software techniques have been provided for correcting problems associated with speculative exceptions. However, each technique brings with it an associated overhead. The hardware technique utilizes chip area for control and pipelining of data. The software technique requires compute cycles for determining whether the exception handler need, in fact be executed, thus reducing the performance of the computer system. It is desirable to reduce the number of speculative exceptions to thereby minimize the overhead incurred by the software and hardware exception handling techniques.